//
//  main.c
//  Questions
//
//  Created by wangrui on 14-09-18.
//  Copyright (c) 2014年 PPS. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include "cutils.h"

#define INF 999999


/*二维数组的指针不能这样传进来,因为这个要限制数组列的大小
void printMatrix(int (*matrix)[100], int m, int n)
{
	for (int i=1; i<=m; i++) {
		for (int j=1; j<=n; j++) {
			printf("%-6d ", * (*(matrix+i)+j));  //martrix 为指向数组的指针，matrix+1指向下一个 大小为100的数字。
												 // *matrix+i 指向第一个一维数组的首地址
		}
		printf("\n");
	}
}*/


typedef struct {
	queue_t que;
}Path;

void createPath(Path * p){
	init_queue(&(p->que));
}

void enqueuePath(Path *p, int *value){
	enqueue(p->que, value);
}

void destroyPath(Path *p) {
	destory_queue(p->que);
}

void printPath(Path *p) {
	
	while (!is_empty_queue(p->que)) {
		int *out = dequeue(p->que, NULL);
		printf("%d->",*out);
		free(out);
	}	
}

void printMatrix(int *martix, int m, int n){
	for (int i=1; i<m; i++) {
		for (int j=1; j<n; j++) {
			printf("%-6d ",*(martix+m*i+j));
		}
		
		printf("\n");
	}
	
	printf("\n");
}

int main(int argc, const char * argv[])
{
	int v,e;//顶点数，边数
	scanf("%d %d",&v,&e);
	
	int matrix[v+1][v+1];
	
	//初始化
	for (int i=0; i<=v; i++) {
		
		for (int j=0; j<=v; j++) {
			
			if (i==0 || j==0 || i==j) {
				matrix[i][j] = 0;
			}
			else{
				matrix[i][j] = INF;
			}
		}
	}
	

	//读入边
	for (int i=0; i<e; i++) {
		int t1,t2,t3;
		scanf("%d %d %d",&t1,&t2,&t3); //t1 到 t2, 的距离 t3
		matrix[t1][t2] = t3;
	}
	

	
	/*测试
	 *
	//printMatrix(&matrix[0][0], v+1, v+1); //强行传第一个地址
	//printMatrix(&matrix[0][0], v+1, v+1);
	 
	//经过一号顶点
	for (int i=1; i<=v; i++) {
		for (int j=1; j<=v; j++) {
			if (matrix[i][j] > matrix[i][1] + matrix[1][j]) {
				matrix[i][j] = matrix[i][1] + matrix[1][j];
			}
		}
	}
	printMatrix(&matrix[0][0], v+1, v+1);
	
	
	//经过1,2号顶点
	for (int i=1; i<=v; i++) {
		for (int j=1; j<=v; j++) {
			if (matrix[i][j] > matrix[i][2] + matrix[2][j]) {
				matrix[i][j] = matrix[i][2] + matrix[2][j];
			}
		}
	}
	printMatrix(&matrix[0][0], v+1, v+1);
	 *
	 */
	
	//初始化指针
	Path pathes[v+1][v+1];
	for (int i=0; i<=v; i++) {
		for (int j=0; j<=v; j++) {
			pathes[i][j].que = NULL;
		}
	}
	
	for (int k=1; k<=v; k++) {
		for (int i=1; i<=v; i++) {
			for (int j=1; j<=v; j++) {
				if (matrix[i][j] > matrix[i][k] + matrix[k][j]) { //经过第k点 中转
					matrix[i][j] = matrix[i][k] + matrix[k][j];
					
					//记录中转点
					int *point = (int *)malloc(sizeof(int));
					*point = k;
					if (pathes[i][j].que == NULL) {
						createPath(&pathes[i][j]);
					}
					enqueuePath(&pathes[i][j], point);
				}
			}
		}
	}
	
	printf("\n");
	printf("the nearest martrix is:\n");
	printMatrix(&matrix[0][0], v+1, v+1);
	
	
	//打印最短路径
	int src,dst;
	printf("intput the start and arrive point:\n");
	scanf("%d %d",&src,&dst);
	
	printf("the shortest distance is %d \n",matrix[src][dst]);
	printf("the shortest path is: %d->",src);
	
	printPath(&pathes[src][dst]);
	destroyPath(&pathes[src][dst]);
	printf("%d \n",dst);
	
	return 0;
}


